#include <climits>
#include <cstdio>
/*
int max(int a, int b);
struct good_info {
    int weight;
    int value;
} data_info[101];
int dp[101][1001];

int main(int argc, char const* argv[])
{
    int s, n;
    while (scanf("%d%d", &s, &n) != EOF) {
        for (int i = 1; i <= n; i++)
            scanf("%d%d", &data_info[i].weight, &data_info[i].value);
        for (int i = 0; i <= s; i++)
            dp[0][i] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = s; j >= data_info[i].weight; j--)
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - data_info[i].weight] + data_info[i].value);
            for (int j = data_info[i].weight - 1; j >= 0; j--)
                dp[i][j] = dp[i - 1][j];
        }
        printf("%d\n", dp[n][s]);
    }
    return 0;
}

int max(int a, int b) { return a > b ? a : b; }
*/
/*
抽象出一个帮助理解的场景：
选取前i-1个物体，决定哪些需要放入背包时，在该轮活动抽象出一个具体的背包：使背包大小动态变化，从而当每个背包大小确定时，具体放入的物品情况也能确定。
现在开始考虑第i个物品的放入，那么可以再抽象出一个背包：使背包大小动态变化，同时参考上一个背包放入情况进行新背包的物品情况。
当要求恰好装满背包时，初始条件需要变化为dp[0][0] = 0, 其他dp[0][i]为不存在
*/
/*
但实际上，我们并不关心当确定前i个物品可以放入背包时，背包中物品的具体情况；而只是关心在背包动态变化的过程中，每确定一个背包大小，就有对应的物品最大价值。
代码如下，注意需要倒序更新(这个地方还没想的特别清楚，大概新加入一个可选物品时，在变化背包大小时，需要保证用来对比的数据(dp[j-data_info[i].weight]])是未放入该物品时的情况)
但还需注意的是，若为完全背包问题，反而应该顺序更新。
*/

int max(int a, int b);
struct good_info {
    int weight;
    int value;
} data_info[101];
int dp[1001];

int main(int argc, char const* argv[])
{
    int s, n;
    while (scanf("%d%d", &s, &n) != EOF) {
        for (int i = 1; i <= n; i++)
            scanf("%d%d", &data_info[i].weight, &data_info[i].value);
        for (int i = 0; i <= s; i++)
            dp[i] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = s; j >= data_info[i].weight; j--)
                dp[j] = max(dp[j], dp[j - data_info[i].weight] + data_info[i].value);
            for (int j = data_info[i].weight - 1; j >= 0; j--)
                dp[j] = dp[j];
        }
        printf("%d\n", dp[s]);
    }
    return 0;
}

int max(int a, int b) { return a > b ? a : b; }